{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "08f3859b-9bac-489c-8e6b-1cdf4dc8f854",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "# 问题引入     \n",
    "       一家餐馆的啤酒售价为5元一瓶。近期节日有促销活动，喝完啤酒后，\n",
    "       可以用5个空瓶或10个瓶盖换购一瓶啤酒。\n",
    "       此外，消费满100元可以再送一瓶啤酒。\n",
    "       现有200元，最多可以喝多少瓶啤酒？"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2db14237-1cd7-447e-8056-085c6420b317",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "# 方法0 (亲自体验)\n",
    "\n",
    "最终喝了58瓶酒  余 8 个盖 和 3个瓶, 继续借酒换\n",
    " \n",
    "| | 步骤 | 钱 | 盖数A<sub>n</sub> | 瓶数B<sub>n</sub> | 累计酒数C<sub>n</sub> |\n",
    "| --- | --- | --- | --- | --- | --- |\n",
    "| 0 | 送的酒换成钱 | 210 | 0 | 0 | 0 |\n",
    "| 1 | 210元买酒 | 0 | 42 | 42 | 42 |\n",
    "| 2 | 换酒 | 0 | 14 | 14 | 42+(4+8) |\n",
    "| 3 | 换酒 | 0 | 7 | 7 | 42+(4+8)+(1+2) |\n",
    "| 4 | 换酒 | 0 | 8 | 3 | 42+(4+8)+(1+2)+(0+1)=58 |\n",
    "| 5 | 借老板2瓶酒 | 0 | 10 | 5 | 58+2=60 |\n",
    "| 6 | 还老板2瓶酒 | 0 | 0 | 0 | 60 |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "863fb8c6-b252-4b78-b25f-6aa6f3131f18",
   "metadata": {},
   "source": [
    "# 方法1 （口算法）\n",
    "\n",
    "把  钱, 盖, 瓶 , 酒  全部转换为同样的单位---瓶酒盖(U)\n",
    "\n",
    "1瓶酒盖=1瓶+1酒+1盖=1U\n",
    "\n",
    "1元=0.2U\n",
    "\n",
    "1盖=0.1U\n",
    "\n",
    "1瓶=0.2U\n",
    "\n",
    "1酒=1U-1盖-1瓶=(1-0.1-0.2)U=0.7U\n",
    "\n",
    "初始资产=210元=42U\n",
    "\n",
    "喝的酒数=初始资产/1酒=42U/0.7U=60"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "bd9dc53b-047c-4e93-bb01-f8ce5c07a945",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1盖=1/2元\n",
      "1酒=7/2元\n",
      "1瓶=1元\n",
      "共可以喝 60 瓶酒\n"
     ]
    }
   ],
   "source": [
    "# 方法2  (线性方程组)\n",
    "from sympy import symbols, linsolve\n",
    "# 定义符号变量\n",
    "# 1元=1元\n",
    "# 1盖=x元\n",
    "# 1酒=y元\n",
    "# 1瓶=z元\n",
    "# 若初始资产为A元,则答案为 A/y\n",
    "x, y, z, A = symbols('x y z A')\n",
    "\n",
    "# 创建线性方程组\n",
    "eq1 = 42*(x+y+z) - A\n",
    "eq2 = x + y + z - 10*x\n",
    "eq3 = x + y + z - 5*z\n",
    "eq4 = x + y + z - 5\n",
    "\n",
    "# 求解线性方程组\n",
    "result = linsolve([eq1, eq2, eq3, eq4], (x, y, z, A))\n",
    "# 提取解集中的值\n",
    "rx,ry,rz,rA = result.args[0]\n",
    "\n",
    "# 打印解\n",
    "print(f\"1盖={rx}元\")\n",
    "print(f\"1酒={ry}元\")\n",
    "print(f\"1瓶={rz}元\")\n",
    "print(f\"共可以喝 {rA/ry} 瓶酒\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "b0b64392-489f-46ed-a3bf-5ae5bce0e1aa",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "状态: 1\n",
      "最多可以喝到的啤酒数量: 60\n",
      "购买的啤酒数量: 40\n",
      "用空瓶兑换的啤酒数量: 12\n",
      "用瓶盖兑换的啤酒数量: 6\n",
      "满100元赠送的啤酒数量: 2\n",
      "剩余的空瓶数量: 0\n",
      "剩余的瓶盖数量: 0\n"
     ]
    }
   ],
   "source": [
    "# 方法3  (线性规划)\n",
    "from pulp import LpMaximize, LpProblem, LpVariable, lpSum,GLPK\n",
    "# 创建最大化问题\n",
    "prob = LpProblem(\"Beer_Optimization\", LpMaximize)\n",
    "# 定义决策变量\n",
    "x_purchase = LpVariable(\"x_purchase\", lowBound=0, cat='Integer')  # 购买的啤酒数量\n",
    "x_bottle = LpVariable(\"x_bottle\", lowBound=0, cat='Integer')    # 用空瓶兑换的啤酒数量\n",
    "x_cap = LpVariable(\"x_cap\", lowBound=0, cat='Integer')        # 用瓶盖兑换的啤酒数量\n",
    "x_gift = LpVariable(\"x_gift\", lowBound=0, upBound=4, cat='Integer')  # 满100元赠送的啤酒数量，最多4瓶\n",
    "b_left = LpVariable(\"b_left\", lowBound=0, cat='Integer')      # 剩余的空瓶数量\n",
    "c_left = LpVariable(\"c_left\", lowBound=0, cat='Integer')      # 剩余的瓶盖数量\n",
    "# 目标函数：最大化总啤酒数量\n",
    "prob += x_purchase + x_bottle + x_cap + x_gift, \"Total_Beers\"\n",
    "# 约束条件\n",
    "prob += 5 * x_purchase <= 200, \"Budget_Constraint\"  # 预算约束\n",
    "# 赠品约束：每满100元送一瓶（等价于每购买20瓶送一瓶）\n",
    "# 正确表达 x_gift = x_purchase // 20 的约束\n",
    "prob += x_purchase >= 20 * x_gift, \"Div_Constraint_1\"\n",
    "prob += x_purchase <= 20 * (x_gift + 1) - 1, \"Div_Constraint_2\"  # 修改这里\n",
    "# 空瓶和瓶盖的产生与使用平衡约束\n",
    "prob += b_left == x_purchase + x_bottle + x_cap + x_gift - 5 * x_bottle, \"Bottle_Balance\"\n",
    "prob += c_left == x_purchase + x_bottle + x_cap + x_gift - 10 * x_cap, \"Cap_Balance\"\n",
    "# 最终剩余的空瓶和瓶盖数量非负\n",
    "prob += b_left >= 0, \"NonNegative_Bottles\"\n",
    "prob += c_left >= 0, \"NonNegative_Caps\"\n",
    "# 使用 GLPK 求解器并关闭日志\n",
    "prob.solve(GLPK(msg=False))\n",
    "# 输出结果\n",
    "print(\"状态:\", prob.status)\n",
    "print(\"最多可以喝到的啤酒数量:\", prob.objective.value())\n",
    "print(\"购买的啤酒数量:\", x_purchase.value())\n",
    "print(\"用空瓶兑换的啤酒数量:\", x_bottle.value())\n",
    "print(\"用瓶盖兑换的啤酒数量:\", x_cap.value())\n",
    "print(\"满100元赠送的啤酒数量:\", x_gift.value())\n",
    "print(\"剩余的空瓶数量:\", b_left.value())\n",
    "print(\"剩余的瓶盖数量:\", c_left.value())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7776cfc0-02e2-4277-a4dc-d8f4db795ddc",
   "metadata": {},
   "source": [
    "# 换酒定理 (构造具体的换法)\n",
    "\n",
    "\n",
    "$\\color{red}{酒换干净的充要条件 是 初始资产可换整瓶酒b 并且 方法2 的解s=A/y为整数}$ \n",
    "\n",
    "如果没有这个换酒定理,上面的方程组解法是不严谨的,并有可能是错的。\n",
    "\n",
    "下面构造的换法是为借老板s-b瓶酒一步到位,不用像方法一那样换来换去了。\n",
    "\n",
    "换酒定理回答了方法2算出的解是否可靠,在现实中是否可操作\n",
    "\n",
    "下面构造换法\n",
    "\n",
    "约定:\n",
    "\n",
    "P1: 初始资产可换b瓶酒\n",
    "\n",
    "P2: 方法2的解A/y=s\n",
    "\n",
    "P3: 借老板t瓶酒\n",
    "\n",
    "初始资产+借老板的资产=喝进肚子酒的资产+还老板的资产\n",
    "\n",
    "b(x+y+z) +t(x+y+z) =s*y+s*(x+z)\n",
    "\n",
    "只要t是整数,就存在换法\n",
    "\n",
    "t=s-b \n",
    "\n",
    "因为s是喝的酒数, 现实中s必须为整数\n",
    "\n",
    "所以s和b都为整数才能换干净\n",
    "\n",
    "根据换酒定理构造的换酒步骤如下:\n",
    "\n",
    "先喝下210元买的42瓶酒\n",
    "\n",
    "借老板18瓶酒,并喝下,此时已经喝下了60瓶酒\n",
    "\n",
    "把手上的60个瓶和60个盖子还给老板,抵消借老板的18瓶酒\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.21"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
